package simpleTest;

import java.util.Arrays;

public class sortTest {
    public static void main(String[] args) {
        int arr[] = {0, 12, 88, -6, 55, -3, 62, 30, 108};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    public static void quickSort(int[] arr, int left, int right) {
        //即长度为1结束递归
        if (left>=right){
            return;
        }
        int r = right;
        int l = left;
        int pivot = arr[l];
        while (l < r) {
            //右边遍历寻找比prvot小的值
            while (pivot <= arr[r] && l < r) {
                r--;
            }
            //从左边遍历寻找比prvot大的值
            while (pivot >= arr[l] && l < r) {
                l++;
            }
            //交换
            if (l < r) {
                int temp = arr[l];
                arr[l] = arr[r];
                arr[r] = temp;
            }
        }
        //最后将l==r位置与基准位置交换
        arr[left] = arr[r];
        arr[r] = pivot;
        //开始处理基准位左边数据左边递归
        quickSort(arr, left, r - 1);
        //右边递归
        quickSort(arr, r + 1, right);
    }
}
